package com.xiaolin.algorithm.recursion;

import java.util.Vector;

/**
 * @ClassName ClimbStairs
 * @Description 递归实现爬楼梯的爬法种类（斐波那契数列）
 * @Detail  规定爬楼梯每次只能爬一个台阶或两个台阶
 *                  总结：
 *                      有相同子问题的递归，可以用动态规划的备忘录思想是树形递归结构转成线型递归结构，防止重复递归，提高性能
 * @Author MyPC
 * @Date 2020/11/20
 * @Version 1.0
 */
public class ClimbStairs {
    public static void main(String[] args) {
//        long s1 = System.currentTimeMillis();
//        System.out.println(climb(50));   // 耗时 42999 毫秒
//        System.out.println(System.currentTimeMillis()-s1);
        long s2 = System.currentTimeMillis();
        System.out.println(climbClearChildProblem(50));  // 耗时 0 毫秒
        System.out.println(System.currentTimeMillis()-s2);
        long s3 = System.currentTimeMillis();
        System.out.println(climbUseMemoTable(50));  // 耗时 0 毫秒
        System.out.println(System.currentTimeMillis()-s3);
        long s4 = System.currentTimeMillis();
        System.out.println(climbSavePreTwoStatus(50));  // 耗时 0 毫秒
        System.out.println(System.currentTimeMillis()-s4);
    }

    /**
     * 爬楼梯，使用最简单的递归，会重复计算子问题，时间复杂度为O(2^n),程指数增长，算法低效
     * @param stairs  台阶数
     * @return
     */
    public static long climb(int stairs){
        if(stairs==1 || stairs == 2)return stairs;
        return climb(stairs-1)+climb(stairs-2);
    }

    /**
     * 使用递归，消除子问题，使时间复杂度变为O(n)，核心就是添加备忘录
     * @param stairs
     * @return
     */
    public static long climbClearChildProblem(int stairs){
        // 用于存放子问题的结果，只要算出一个子问题，其他相同的子问题就无需计算了
        long[] memo=new long[stairs+1];   // 数组长度比层级+1是防止层级与数组索引对应时，计算最后一级台阶的种类是发生索引越界
        return recursion(stairs,memo);
    }

    /**
     * 递归求出爬楼梯种类，时间复杂度O(n)
     * @param stairs
     * @param memo
     * @return
     */
    public static long recursion(int stairs,long[] memo){
        if(stairs==1 || stairs == 2)return stairs;
        //判断相同的子问题是否以前计算过，如果以前算过，直接返回结果
        if(memo[stairs] != 0){
            return memo[stairs];
        }
        // 将子问题的计算结果保存一份
        memo[stairs]= recursion(stairs-1,memo)+recursion(stairs-2,memo);
        return memo[stairs];
    }

    /**
     * 使用备忘录表，实现自底向上的推算,时间复杂度O(n)
     * @param stairs
     * @return
     */
    public static Long climbUseMemoTable(int stairs){
        if(stairs==0)return 0L;
        if(stairs==1 || stairs ==2)return (long)stairs;
        // 备忘录表，阶梯层级与数组索引下标一一对应
        long[] memo=new long[stairs+1];
        memo[1]=1;
        memo[2]=2;
        for (int i=3;i<=stairs;i++){
            // 自底向上推出结果
            memo[i]=memo[i-1]+memo[i-2];
        }
        return memo[stairs];
    }

    /**
     * 不使用备忘录表,只需存储前两个的计算结果即可，实现时间复杂度为O(n),但空间复杂度为O(1)
     * @param stairs
     * @return
     */
    public static Long climbSavePreTwoStatus(int stairs){
        if(stairs==0)return 0L;
        if(stairs==1 || stairs ==2)return (long)stairs;
        // 每次只开辟一次空间，不管台阶数量多少
        // 存放运算结果
        long sum=0;
        // 存放f(n-2)的值
        long f=1;
        // 存放f(n-1)的值
        long n=2;
        for (int i=3;i<=stairs;i++){
            sum=f+n;
            // 将f(n-2)的值存到f(n-1)
            f=n;
            // 将运算结果存到f(n-2)
            n=sum;
        }
        return sum;
    }
}
